import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 1685. 有序数组中差绝对值之和
 * https://leetcode-cn.com/problems/sum-of-absolute-differences-in-a-sorted-array/
 */
public class Solutions_1685 {
    public static void main(String[] args) {
        int[] nums1 = {2, 3, 5};  // output: {4, 3, 5}
        int[] nums2 = {1, 4, 6, 8, 10};  // output: {24, 15, 13, 15, 21}

        List<int[]> inputs = new ArrayList<>();
        inputs.add(nums1);
        inputs.add(nums2);

        for (int[] input : inputs) {
            int[] result = getSumAbsoluteDifferences(input);
            System.out.println(Arrays.toString(result));
        }
    }

    /**
     * 解法二：数学（前缀和）（3ms）
     * 以 {1, 4, 6, 8, 10}，res[2] = 13 为例
     * res[2] = (左侧元素个数 * 当前元素 - 前缀和) +
     *          (总和 - 前缀和 - 当前元素 - 右侧元素个数 * 当前元素)
     *        = 2 * 6 - 5 +
     *          29 - 5 - 6 - 2 * 6
     *        = 7 + 6 = 13
     * 左边部分：(左侧元素个数 * 当前元素 - 前缀和)
     * 右边部分：(总和 - 前缀和 - 当前元素 - 右侧元素个数 * 当前元素)
     * 关键：根据前缀和计算出绝对值之和
     *      {1, 4, 6}
     *      6 与数组其他元素的绝对值之和为：其他元素个数 * 6 - 前缀和
     */
    public static int[] getSumAbsoluteDifferences(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        int preSum = 0;
        int len = nums.length;
        int[] res = new int[len];
        for (int i = 0; i < len; i++) {
            // 左侧部分绝对值之和
            int left = i * nums[i] - preSum;
            // 右侧部分绝对值之和
            int right = sum - preSum - nums[i] - (len - i - 1) * nums[i];
            res[i] = left + right;
            preSum += nums[i];
        }
        return res;
    }

    /**
     * 解法一：数学（7ms）
     * 根据 res[0]，推导出 res[1]
     * 根据 res[1]，推导出 res[2]
     * ...
     * 关键：索引 1 相比索引 0 来说，索引 1 与后面索引上的元素更近了（减法）
     * 与前面索引上的元素更远了（加法）
     */
    public static int[] getSumAbsoluteDifferences2(int[] nums) {
        int len = nums.length;
        int[] res = new int[len];
        for (int i = 1; i < len; i++) {
            res[0] += nums[i] - nums[0];
        }
        for (int i = 1; i < len; i++) {
            res[i] = res[i - 1];
            int diff = nums[i] - nums[i - 1];

            // 右边有 rightCnt 个元素，差值为 diff * rightCnt
            int rightCnt = len - (i + 1);
            res[i] -= diff * rightCnt;

            // 左边有 i 个元素，差值为 diff * (i - 1)
            res[i] += diff * (i - 1);
        }
        return res;
    }
}
